package Solution125_150;

import org.junit.Test;

import java.util.*;

public class Solution139单词拆分 {
    public boolean wordBreak2(String s, List<String> wordDict) {
        /*为了判断判方便*/
        Map<Character, List<String>> wordMap = new HashMap<>();
        for (String w : wordDict) {
            if (w == null || w.length() == 0) {
                continue;
            }
            char kc = w.charAt(0);
            if (wordMap.containsKey(kc)) {
                wordMap.get(kc).add(w);
            } else {
                List<String> l = new ArrayList<>();
                l.add(w);
                wordMap.put(kc, l);
            }
        }
        int curIndex = 0;
        return dfs(s, curIndex, wordMap);
    }

    private boolean dfs(String s, int curIndex, Map<Character, List<String>> wordMap) {
        if (curIndex == s.length()) {
            return true;
        }
        if (curIndex > s.length()) {
            return false;
        }
        char curK = s.charAt(curIndex);
        if (!wordMap.containsKey(curK)) {
            return false;
        }
        for (String subStr : wordMap.get(curK)) {
            if (curIndex + subStr.length() > s.length()) {
                continue;
            }
            String tempS = s.substring(curIndex, curIndex + subStr.length());
            if (tempS.equals(subStr)) {
                boolean tempResult = dfs(s, curIndex + subStr.length(), wordMap);
                if (tempResult) {
                    return tempResult;
                }
            }
        }
        return false;

    }

    @Test
    public void test() {
        /**
         * "aaaaaaa"
         * ["aaaa","aa"]
         */
        String s = "aaaaaaa";
        List<String> l = new ArrayList<>();
        l.add("aaaa");
        l.add("aa");
        System.out.println(wordBreak3(s, l));
    }

    public boolean wordBreak3(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int n = s.length();
        boolean[] result = new boolean[n + 1];
        Set<String> ds = new HashSet<>();
        int maxLength = 0;
        for (String s1 : wordDict) {
            ds.add(s1);
            maxLength = Math.max(maxLength, s1.length());
        }
        result[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxLength; j++) {
                if (i - j >= 0 && result[i - j] && ds.contains(s.substring(i - j, i))) {
                    result[i] = true;
                    break;
                }
            }
        }
        return result[n];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        Set<String> set = new HashSet<>();
        int maximum = 0;
        for (String str : wordDict) {
            set.add(str);
            maximum = Math.max(maximum, str.length());
        }
        dp[0] = true;
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= maximum; j++)
                /*拆分成两个串， 前面串是可以拆分的，后面串在字典中*/
                if (i - j >= 0 && dp[i - j] && set.contains(s.substring(i - j, i))) {
                    dp[i] = true;
                    break;
                }
        return dp[len];
    }
}
